package Leetcode.DayTest;

import java.util.*;

/**
 * @Author: kirito
 * @Date: 2024/9/25 16:38
 * @Description:
 * 给你一个字符串数组 ideas 表示在公司命名过程中使用的名字列表。公司命名流程如下：
 *
 * 从 ideas 中选择 2 个 不同 名字，称为 ideaA 和 ideaB 。
 * 交换 ideaA 和 ideaB 的首字母。
 * 如果得到的两个新名字 都 不在 ideas 中，那么 ideaA ideaB（串联 ideaA 和 ideaB ，中间用一个空格分隔）是一个有效的公司名字。
 * 否则，不是一个有效的名字。
 * 返回 不同 且有效的公司名字的数目。
 *
 * 示例 1：
 *
 * 输入：ideas = ["coffee","donuts","time","toffee"]
 * 输出：6
 * 解释：下面列出一些有效的选择方案：
 * - ("coffee", "donuts")：对应的公司名字是 "doffee conuts" 。
 * - ("donuts", "coffee")：对应的公司名字是 "conuts doffee" 。
 * - ("donuts", "time")：对应的公司名字是 "tonuts dime" 。
 * - ("donuts", "toffee")：对应的公司名字是 "tonuts doffee" 。
 * - ("time", "donuts")：对应的公司名字是 "dime tonuts" 。
 * - ("toffee", "donuts")：对应的公司名字是 "doffee tonuts" 。
 * 因此，总共有 6 个不同的公司名字。
 *
 * 下面列出一些无效的选择方案：
 * - ("coffee", "time")：在原数组中存在交换后形成的名字 "toffee" 。
 * - ("time", "toffee")：在原数组中存在交换后形成的两个名字。
 * - ("coffee", "toffee")：在原数组中存在交换后形成的两个名字。
 */

public class 公司名字 {
    public static void main(String[] args) {
        公司名字 test = new 公司名字();
        String[] arr = {"coffee", "donuts", "time", "toffee"};
        System.out.println(test.distinctNames(arr));
    }

    /**
     *什么样的一对字符串无法交换首字母？
     *
     * 示例 1 中的 coffee 和 time，虽然这样两个字符串完全不一样，但如果交换了 coffee 和 time 的首字母，
     * 会得到字符串 toffee，它在数组 ideas 中，不符合题目要求。
     *
     * 又例如 ideas=[aa,ab,ac,bc,bd,be]，将其分成两组：
     *
     * 第一组：aa,ab,ac。
     * 第二组：bc,bd,be。
     * 其中第一组内的字符串是不能交换首字母的，因为交换后字符串不变，必然在 ideas 中。第二组也同理。
     *
     * 考虑交换第一组的字符串和第二组的字符串，哪些是可以交换首字母的，哪些是不能交换首字母的？
     *
     * 第一组的 ac 无法和第二组的任何字符串交换，因为交换后会得到 bc，它在 ideas 中。
     * 第二组的 bc 无法和第一组的任何字符串交换，因为交换后会得到 ac，它在 ideas 中。
     * 其余字符串对可以交换首字母。
     * 上面的分析立刻引出了如下方法
     *
     * 方法一：按照首字母分组
     * 按照首字母，把 ideas 分成（至多）26 组字符串。
     *
     * 例如 ideas=[aa,ab,ac,bc,bd,be] 分成如下两组（只记录去掉首字母后的字符串）：
     *
     * A 组（集合）：{a,b,c}。
     * B 组（集合）：{c,d,e}。
     * 分组后：
     *
     * 从 A 中选一个不等于 c 的字符串，这有 2 种选法。
     * 从 B 中选一个不等于 c 的字符串，这有 2 种选法。
     * 考虑两个字符串的先后顺序（谁在左谁在右），有 2 种方法。
     * 根据乘法原理，有 2×2×2=8 对符合要求的字符串。
     *
     * 由于无法选交集中的字符串，一般地，从 A 和 B 中可以选出
     *
     * 2⋅(∣A∣−∣A∩B∣)⋅(∣B∣−∣A∩B∣)
     * 对符合要求的字符串。其中 ∣S∣ 表示集合 S 的大小。
     *
     * 枚举所有组对，计算上式，累加到答案中。
     * 灵神！
     */
    public long distinctNames(String[] ideas) {
        Set<String>[] groups = new HashSet[26];
        Arrays.setAll(groups, i -> new HashSet<>());
        for (String s : ideas) {
            groups[s.charAt(0) - 'a'].add(s.substring(1)); // 按照首字母分组
        }

        long ans = 0;
        for (int a = 1; a < 26; a++) { // 枚举所有组对
            for (int b = 0; b < a; b++) {
                int m = 0; // 交集的大小
                for (String s : groups[a]) {
                    if (groups[b].contains(s)) {
                        m++;
                    }
                }
                ans += (long) (groups[a].size() - m) * (groups[b].size() - m);
            }
        }
        return ans * 2; // 乘 2 放到最后
    }

    //暴力模拟
    public long distinctNames_false(String[] ideas) {
        long ans = 0;
        int n = ideas.length;
        Map<String, String> map = new HashMap<>();
        for (String s : ideas) {
            map.put(s, s);
        }
        for (int i = 0; i < n - 1; i++) {
            String s1 = ideas[i];
            char c1 = s1.charAt(0);
            char[] chars1 = s1.toCharArray();

            for (int j = i + 1; j < n; j++) {
                String s2 = ideas[j];
                char c2 = s2.charAt(0);
                char[] chars2 = s2.toCharArray();
                chars1[0] = c2;
                chars2[0] = c1;
                String newS1 = new String(chars1);
                String newS2 = new String(chars2);
                System.out.print(newS1 + "   " + newS2+"   ");
                System.out.println(map.get(newS1) == null && map.get(newS2) == null);
                if (map.get(newS1) == null && map.get(newS2) == null) {
                    ans += 2;
                }
            }

        }
        return ans;
    }
}
